Problem 409 Longest Palindrome
该问题属于回文问题,要求找出所给字符串提供的字符所能组成的最长的回文序列的长度
主要思路:
该题最初的想法是,回文中字母为奇数的字母只能有1个,将其置于最中心,其余的均为偶数,对称排列组成的回文序列即为最长.可是这里忽略了其实奇数个数量-1即可变成偶数个数量,只要抓住这个关键就能整理出思路.同时还要注意没有字母数量为奇数的情况.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31class Solution {
public int longestPalindrome(String s) {
int[] alpha = new int[52];
char[] c = s.toCharArray();
int result = 0;
if(s.length()==0||s.length()==1)
return s.length();
for (char value : c) {
if (value >= 65 && value <= 90) {
alpha[value - 39]++;
} else {
alpha[value - 97]++;
}
}
int maxOdd = 0;
for (int i=0;i<alpha.length;i++){
if(alpha[i]%2==0){
result += alpha[i];
}else {
if(alpha[i]>maxOdd){
maxOdd = alpha[i];
}
if (alpha[i]>0)
result += (alpha[i]-1);
}
}
if(maxOdd!=0)
result += 1;
return result;
}
}
Problem 415 Add Strings
该问题是字符串相加问题,该问题自然不用考虑使用系统函数之类的方法,因为一定会出现相加之后溢出的测试用例.那么按照以下步骤处理即可:
- 比较两个字符串长度,将短的一方前方补充0以对齐
- 从尾部开始对数据进行相加,如果遇到相加大于等于10的情况,注意设置进位flag用于下一位的进位使用
只要把握以上两点,该问题基本上很清楚了,该题主要用一些细节,比如char转int和int转char的问题,其中char转int较为简单,利用ASCII码相减即可.而int转char不能直接使用(char)num的形式,这样会出现unicode字符,可以使用(char)(num+’0’).
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55class Solution {
public String addStrings(String num1, String num2) {
boolean carry = false;
if (num1.equals("") ||num1==null){
return num2;
}
if (num2.equals("") ||num2==null){
return num1;
}
if (num1.length() > num2.length()) {
num2 = paddingStr(num1, num2);
} else {
num1 = paddingStr(num1, num2);
}
char[] result = new char[num1.length()+1];
for (int i=result.length-1;i>=0;i--){
int sum = (i>0?convertStrToInt(num1.charAt(i-1)):0)+(i>0?convertStrToInt(num2.charAt(i-1)):0);
if (carry){
sum += 1;
if (sum>=10){
carry = true;
result[i] = (char)((sum-10)+'0');
}else {
carry = false;
result[i] = (char)(sum+'0');
}
}else {
if (sum>=10){
carry = true;
result[i] = (char)((sum-10)+'0');
}else {
carry = false;
result[i] = (char)(sum+'0');;
}
}
}
String s = String.valueOf(result);
if(s.charAt(0)=='0')
return s.substring(1,s.length());
return s;
}
public String paddingStr(String s1,String s2){
StringBuilder zero = new StringBuilder();
for (int i=0;i<Math.abs(s1.length()-s2.length());i++){
zero.append("0");
}
zero.append(s1.length()>s2.length()?s2:s1);
return zero.toString();
}
public int convertStrToInt(char c){
return c-48;
}
}
⭐Problem 429 N-ary Tree Level Order Traversal
该问题是经典的树的层序遍历问题,只不过此处不是二叉树,而是多叉树,但是原理与二叉树相同,都可以利用队列来存放结点,通过入队出队的方式对结点进行读取.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
if(root == null){
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> temp = new ArrayList<>();
for(int i = 0;i < size;i++){
Node node = queue.poll();
temp.add(node.val);
List<Node>child = node.children;
if(child == null || child.isEmpty())
continue;
for (Node value : child) {
queue.offer(value);
}
}
result.add(temp);
}
return result;
}
}
代码说明:
以 1
3 2 4
5 6 为例
最初是1号结点入队,queue的offer方法功能与add相同,只不过其在队满时再添加元素的话返回false,而add直接返回null.此时进入队列,获得队列长度,此时的长度就是该层所有结点的数量.1的子结点包括3、2、4,它们进入队列,之后3出列,查找其子结点,5、6入队,此时队列中为2、4、5、6,但是由于前面有queue.size()控制每层的数量,所以此时不必担心每层多计算结点.